class TreeNode():
    def __init__(self, data=None, leftPointer=None,rightPointer=None):
        self.data = data
        self.leftPointer = leftPointer
        self.rightPointer = rightPointer

def outputTree(thisPtr):
    if thisPtr == -1:
        return
    else:
        outputTree(binaryTree[thisPtr].leftPointer)
        print(binaryTree[thisPtr].data)
        outputTree(binaryTree[thisPtr].rightPointer)



def findNode(searchItem):
    thisPtr = rootPointer
    while thisPtr!=-1 and binaryTree[thisPtr].data != searchItem:
            if searchItem>binaryTree[thisPtr].data:
                thisPtr = binaryTree[thisPtr].rightPointer
            else:
                thisPtr = binaryTree[thisPtr].leftPointer
    return thisPtr

def findNodeReturnFlag(searchItem):
    flag = False
    thisPtr = rootPointer
    while thisPtr!=-1:
            if searchItem>binaryTree[thisPtr].data:
                thisPtr = binaryTree[thisPtr].rightPointer
            elif searchItem < binaryTree[thisPtr].data:
                thisPtr = binaryTree[thisPtr].leftPointer
            else:
                return True
    return flag

def insertNode(newItem):
    global freePtr
    global rootPointer
    if freePtr != -1:
        # free update
        newNodePtr = freePtr                        #新节点指向
        freePtr = binaryTree[freePtr].leftPointer  #更新free
        binaryTree[newNodePtr].data = newItem
        binaryTree[newNodePtr].leftPointer = -1   #默认叶子节点左右子节点都是-1
        binaryTree[newNodePtr].rightPointer = -1

        if rootPointer!=-1:
            thisNodePtr = rootPointer
            while thisNodePtr != -1:
                previousNodePtr = thisNodePtr
                if binaryTree[thisNodePtr].data > newItem:
                    turnedLeft = True
                    thisNodePtr = binaryTree[thisNodePtr].leftPointer
                else:
                    turnedLeft = False
                    thisNodePtr = binaryTree[thisNodePtr].rightPointer
            if turnedLeft == True:
                binaryTree[previousNodePtr].leftPointer = newNodePtr
            else:
                binaryTree[previousNodePtr].rightPointer = newNodePtr
        else:
            rootPointer = newNodePtr

if __name__ == '__main__':
    rootPointer = 0
    freePtr = 4    #0                      1
    binaryTree = [TreeNode(3,1,2),TreeNode(1,-1,-1),
                   #2                      3
                  TreeNode(5,3,-1),TreeNode(4,-1,-1),
                  #4                        5
                  TreeNode(leftPointer=5),TreeNode(leftPointer=-1)]
    outputTree(rootPointer)
    insertNode(2)
    outputTree(rootPointer)
    print(findNodeReturnFlag(4))
























